import java.util.*;

/**
 * 简单布局算法
 *
 * @author xhf
 */
public class SimpleDistribution extends AbstractDistribution {
    public final static int RINGSIDE = (int) Math.pow(2, 32);
    public final static int NUM_VNODE = 150;
    public final static int STEP = RINGSIDE / NUM_VNODE;

    SimpleDistribution() {
        this.virtualNodes = new ArrayList<>();
    }

    int binarySearch(int target, int start, int end) {
        if (start > end) {
            // 不符合的直接使用第0个位置
            return 0;
        }

        int mid = start + (end - start) / 2;
        VirtualNode midNode = this.virtualNodes.get(mid);
        if (target == midNode.pos) {
            return mid;
        } else if (target < midNode.pos) {
            if (start == mid || start + 1 == mid) {
                return mid;
            }
            return binarySearch(target, start, mid);
        } else {
            return binarySearch(target, mid + 1, end);
        }
    }

    List<VirtualNode> makeVirtualNodes(List<Node> nodes) {
        List<VirtualNode> virtualNodes = new ArrayList<>(nodes.size() * NUM_VNODE);
        for (Node node : nodes) {
            int initPos = hash(node.ip);
            for (int i = 0; i < NUM_VNODE; i++) {
                int pos = (int)(((long)initPos + STEP * i) % RINGSIDE);
                virtualNodes.add(new VirtualNode(node, pos));
            }
        }
        return virtualNodes;
    }

    @Override
    public void addNodes(List<Node> nodes) {
        // TODO
        // 1.去重
        // 2.并发控制
        if (nodes.size() == 0) {
            return;
        }

        List<VirtualNode> newVirtualNodes = makeVirtualNodes(nodes);
        this.virtualNodes.addAll(newVirtualNodes);
        this.virtualNodes.sort((o1, o2) -> o1.pos - o2.pos);
    }

    @Override
    public void removeNodes(List<Node> nodes) {
        // TODO 考虑并发
        for (Node node : nodes) {
            // 删除元素不能使用for、for-each循环，参考：https://juejin.im/post/6844904127307186184
            virtualNodes.removeIf(virtualNode -> virtualNode.node.ip.equals(node.ip));
        }
    }

    @Override
    public Node search(String key) {
        int target = hash(key);
        int index = binarySearch(target, 0, this.virtualNodes.size() - 1);
        return this.virtualNodes.get(index).node;
    }
}
